package leetcode.dfs;

import java.util.Arrays;

//733. 图像渲染---DFS/BFS
public class FloodFill {

   static int[] dx={-1,0,0,1};
    static int[] dy={0,1,-1,0};
    public static void main(String[] args) {
        int[][] m = {{1,1,1},{1,1,0},{1,0,1}};
        floodFill(m,1,1,2);
        for (int i = 0; i < m.length; i++) {
            for (int j =0;j<m[0].length;j++){
                System.out.print(m[i][j]);
            }
            System.out.println();
        }
    }

    //DFS深度遍历
    public static int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        int oldColor  = image[sr][sc];
        dfs(image,sr,sc,newColor,oldColor);
        return image;
    }

    private static void dfs(int[][] image, int sr, int sc, int newColor, int oldColor) {
        if (sr<0 || sr>=image.length || sc<0 || sc>=image[0].length ||
                //当前位置已经上过色
                newColor==oldColor ||
                //当前位置不和起始位置的颜色一致
                image[sr][sc]!=oldColor
        ){
            return;
        }
        image[sr][sc]=newColor; //上色

        //移动
        for (int i =0;i<4;i++){
            int mx=dx[i]+sr;
            int my=dy[i]+sc;
            dfs(image,mx,my,newColor,oldColor);
        }


    }


    //BFS
}
